class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> hash;
        for(string &str : wordDict)
            hash.insert(str);
        int n = s.size();
        
        // dp[i]表示在[0, i]区间的字符串，能否被字典中的单词拼接而成
        vector<bool> dp(n + 1);

        // 初始化
        dp[0] = true;
        s = " " + s;

        for(int i = 1; i <= n; i++)
        {
            // j 表示最后一个单词的起始位置
            // [0, j - 1]之间的字符串是否能有字典的单词拼成 && j到i之间的字符串是否在字典中
            // 即dp[i] = dp[j - 1] && hash.count(s.substr(j, i - j + 1));
            for(int j = 1; j <= i; j++)
            {
                // if(dp[j - 1] == true && hash.count(s.substr(j, i - j + 1)))
                // {
                //     dp[i] = true;
                //     break;
                // }
                
                dp[i] = dp[j - 1] == true && hash.count(s.substr(j, i - j + 1));
                if(dp[i]) break;
            }
        }
        return dp[n];
    }
};